#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

char offset = 'a';
int tr[M][26], fail[M], idx;
int ed[N], cnt[M];

//词频统计反图优化
// int h[N], e[M], ne[M], tt = 1;
// void add(int a, int b) { e[tt] = b, ne[tt] = h[a], h[a] = tt++; }

// void dfs(int x)
// {
//     for (int i = h[x];i;i = ne[i]) {
//         dfs(e[i]);
//         cnt[x] += cnt[e[i]];
//     }
// }

void insert(const string& s, int& ed)
{
    int p = 0;
    for (char it : s) {
        int c = it - offset;
        if (tr[p][c] == 0) tr[p][c] = ++idx;
        p = tr[p][c];
    }
    ed = p;
}

void setfail()
{
    fail[0] = 0;
    queue<int> q;
    for (int i = 0;i < 26;i++) if (tr[0][i]) { q.push(tr[0][i]); }
    while (!q.empty()) {
        int now = q.front();q.pop();
        for (int i = 0;i < 26;i++)
            if (tr[now][i]) {
                fail[tr[now][i]] = tr[fail[now]][i];
                q.push(tr[now][i]);
            } else tr[now][i] = tr[fail[now]][i];
    }
}

int query(const string& s)
{
    int ans = 0, p = 0;
    for (char it : s) {
        int c = it - offset;
        p = tr[p][c];
        for (int tmp = p;tmp;tmp = fail[tmp])    cnt[tmp]++;
        //cnt[p]++;
    }

    // for (int i = 1;i <= idx;i++)
    //     add(fail[i], i);
    // dfs(0);

    //...
}